package 动态规划;

import org.junit.Test;

public class Solution304 {
    class NumMatrix {
        private int[][] dp = null;

        public NumMatrix(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return;
            }
            int row = matrix.length;
            int col = matrix[0].length;
            dp = new int[row][col];
            dp[0][0] = matrix[0][0];
            for (int i = 1; i < row; i++) {
                dp[i][0] = matrix[i][0] + dp[i - 1][0];
            }
            for (int j = 1; j < col; j++) {
                dp[0][j] = matrix[0][j] + dp[0][j - 1];
            }
            for (int i = 1; i < row; i++) {
                for (int j = 1; j < col; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + matrix[i][j] - dp[i - 1][j - 1];
                }
            }

        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int result = dp[row2][col2];
            if (col1 - 1 >= 0) {
                result -= dp[row2][col1 - 1];
            }
            if (row1 - 1 >= 0) {
                result -= dp[row1 - 1][col2];
            }
            if (col1 - 1 >= 0 && row1 - 1 >= 0) {
                result += dp[row1 - 1][col1 - 1];
            }
            return result;
        }
    }

    @Test
    public void test() {
        NumMatrix matrix = new NumMatrix(new int[][]{
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5}});
        System.out.println(matrix.sumRegion(2, 1, 4, 3));
        System.out.println(matrix.sumRegion(1, 1, 2, 2));
        System.out.println(matrix.sumRegion(1, 2, 2, 4));

    }
}
